"""5.大整数乘法"""
def karatsuba_multiply(x, y):
    """
    Karatsuba算法实现大整数乘法
    """
    # 将整数转换为字符串处理
    x_str = str(x)
    y_str = str(y)

    # 基本情况：如果数字很小，直接相乘
    if len(x_str) == 1 or len(y_str) == 1:
        return x * y

    # 确保两个数字位数相同（补零）
    n = max(len(x_str), len(y_str))
    while len(x_str) < n:
        x_str = '0' + x_str
    while len(y_str) < n:
        y_str = '0' + y_str

    # 如果位数是奇数，调整为偶数
    if n % 2 != 0:
        n += 1
        x_str = '0' + x_str
        y_str = '0' + y_str

    # 分割数字
    mid = n // 2
    a = int(x_str[:mid])
    b = int(x_str[mid:])
    c = int(y_str[:mid])
    d = int(y_str[mid:])

    # 递归计算三个乘积
    ac = karatsuba_multiply(a, c)
    bd = karatsuba_multiply(b, d)
    ad_bc = karatsuba_multiply(a + b, c + d) - ac - bd

    # 合并结果：ac * 10^(2m) + (ad+bc) * 10^m + bd
    result = ac * (10 ** (2 * (n - mid))) + ad_bc * (10 ** (n - mid)) + bd

    return result


def school_method_multiply(x, y):
    """
    传统学校方法（模拟竖式乘法）
    """
    x_str = str(x)
    y_str = str(y)

    result = 0
    n = len(y_str)

    for i in range(n):
        digit = int(y_str[n - 1 - i])
        partial = x * digit * (10 ** i)
        result += partial

    return result


# 测试大整数乘法
print("=== 大整数乘法测试 ===")
x = 123456789
y = 987654321

print(f"数字1: {x}")
print(f"数字2: {y}")

# 使用内置乘法验证
expected = x * y
print(f"内置乘法结果: {expected}")

# Karatsuba算法
karatsuba_result = karatsuba_multiply(x, y)
print(f"Karatsuba算法结果: {karatsuba_result}")
print(f"结果正确性: {karatsuba_result == expected}")

# 传统方法
school_result = school_method_multiply(x, y)
print(f"传统方法结果: {school_result}")
print(f"结果正确性: {school_result == expected}")